package com.guli.common.utils;
/*
 * @Author 罗
 * @date 2020/9/12 - 7:36 上午
 */

import java.util.Comparator;
import java.util.List;

public class QuickSort {


    public static <T> void sort(List<T> list, int left, int right, Comparator<T> comparator) {
        int leftIndex = left;
        int rightIndex = right;
        int middleIndex = (leftIndex + rightIndex) / 2;
        T middle = list.get(middleIndex);
        T temp;
        while (leftIndex < rightIndex) {

            while (comparator.compare(list.get(leftIndex), middle) < 0) {
                leftIndex++;
            }

            while (comparator.compare(list.get(rightIndex), middle) > 0) {
                rightIndex--;
            }

            if (rightIndex == leftIndex) {
                break;
            }

            temp = list.get(leftIndex);
            list.set(leftIndex, list.get(rightIndex));
            list.set(rightIndex, temp);

            if (comparator.compare(list.get(leftIndex), middle) == 0) {
                rightIndex--;
            }

            if (comparator.compare(list.get(rightIndex), middle) == 0) {
                leftIndex++;
            }


        }

        if (rightIndex == leftIndex) {
            leftIndex++;
            rightIndex--;
        }
        /**
         * 防止只有两个相同的元素，造成堆栈溢出异常
         * */
        /*if (leftIndex > rightIndex && (right - left == 1)) {
            return;
        }*/

        if (rightIndex > left) {
            sort(list, left, rightIndex, comparator);
        }

        if (right > leftIndex) {
            sort(list, leftIndex, right, comparator);
        }

    }

    public static <T> void sort(List<T> list, Comparator<T> comparator) {
        if(list.size()>0){

            sort(list, 0, list.size() - 1, comparator);
        }
    }
}
